For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
2answers
31 views

Drawing colored balls

I have a sack with $15$ red balls, $15$ blue balls, $15$ green balls and $15$ yellow balls (balls of the same color are indistingishable). In how many ways can I take $30$ balls from the sack? $\\ ...
1
vote
1answer
21 views

Quick question for proof on unimodal sequence formula in Enumerative Combinatorics

I am looking at page 238 of Stanley's Enumerative Combinatorics where he says that $\#V_n = \#D_n - \#V_n^1$ because every element in $V_n^1$ appears twice as a value of $\Gamma_1$. Can someone ...
3
votes
2answers
78 views

Formal power series coefficient problem

Find the coefficient of: $[x^{33}](x+x^3)(1+5x^6)^{-13}(1-8x^9)^{-37}$ I have figured out that I need to use this identity: $(1-x)^{-k} = \sum\limits_{i>=0} \binom {n+k-1} {k-1} x^n $ But I ...
2
votes
2answers
41 views

Prove this binomial identity using induction

prove this identity: $(1-x)^{-k} = \sum\limits_{i>=0} \binom {n+k-1} {k-1} x^n $ using induction. Verification for k=1 is trivial. assuming k= i, proving the identity when k=i+1 is something i ...
4
votes
2answers
83 views

A fair die is rolled n times. What is the probability that at least 1 of the 6 values never appears?

A fair die is rolled $n$ times. What is the probability that at least 1 of the 6 values never appears? I went about calculating the complement of this, because it seemed to be easier. However, I am ...
0
votes
1answer
53 views

A recurrence for a combinatorial problem

$N$ balls are tossed into $n$ boxes independently. Each ball has a $1/n$ chance of falling into any box.$$P_{N,n}(k):= Pr\{exactly\:k\:empty\:boxes\:after\:N\:balls\:thrown\:into\:n\:boxes\}$$ Show ...
4
votes
1answer
78 views

Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n). The restriction on the first type of bit string is that they must have the same ...
0
votes
1answer
291 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
0
votes
1answer
22 views

proof for Erdős-Szekeres theorem using Dilworth's theorem

Let's review a few definitions: Dilwoths's theorem: Suppose that the length of the longest antichain in the poset $P$ is $r$, then $P$ can be partitioned into $r$ chains. Dilworth's dual theorem: ...
2
votes
0answers
45 views

How many possible six-word sentences

A word is defined as a nonempty (possibly meaningless) sequence of letters. How many $6$-word sentences can be made using each of the $26$ letters of the alphabet exactly once? Generalise the result ...
-1
votes
1answer
27 views

Number of ways to pick $K$ balls? [closed]

Given $M$ type of balls, and for each type there are $N$ unique balls(means all balls of same type are labeled). In how many ways can we pick up $K$ balls out of these $N*M$ balls such that atleast ...
0
votes
0answers
10 views

Existence of two-color paths between boundary vertices in a near-triangulated plane graph with an external face of degree 4

Let G be a plane graph with the following characteristics: It is near-triangulated. It has an external face of degree 4 (i.e. the graph has 4 boundary vertices, a diamond-shaped boundary ring). It ...
0
votes
2answers
39 views

Trying to determine the number of possible combinations for a password

OVERVIEW: Making a secure password. People tend to use dictionary words as a basis for their passwords. People tend to make minor substitutions on their passwords (password -> p@$$w0rd) Assuming ...
2
votes
2answers
937 views

Finding the number of strings which do not contain a certain substring…

I want to know the method of solving the following problem: "How many binary strings of length 10 are there each of which does not contain the pattern '110' ?
2
votes
2answers
82 views

Straight Flush probability with a huge hand.

It's easy to calculate the probability of a straight flush when you're dealt $5$ cards. I'd like to ask for the probability of the same when you're dealt half the deck. I seek $P(\text{straight ...
0
votes
1answer
306 views

Probability of picking exactly one correct from a pool of 6 incorrect and 4 correct

So as the question says. You have 6 incorrect objects and 4 correct ones. What are the odds that, when picking 3 of them at random, you end up with exactly one of them being correct. This seems to be ...
0
votes
0answers
9 views

Chernoff type bounds for negative binomial distribution

If I recall correctly I remember reading that we cannot get Chernoff type results for the negative binomial distribution because of something regarding lebesque measure. I don't quite know all the ...
0
votes
1answer
19 views

Integrality conditions and proof by double counting.

Theorem $\mathbf{3.4.}$ In a block design of type $2-(v,k,\lambda)$ every element lies in precisely $r$ blocks, where $$r(k-1)=\lambda(v-1)\textit{ and }bk=vr\;.$$ The letter $r$ stands for ...
5
votes
1answer
509 views

Permutations of a set with a conditional subset

Using the digits 1, 2, 3, 5, 6, 8, 0 only once, how many 4-digit numbers could be constructed if the number is even? This is an exercise from an online course I'm taking. The given solution suggests ...
0
votes
0answers
83 views

How to improve my these specific math skills? [closed]

I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite ...
2
votes
1answer
75 views

$\prod_{ p\leq x}p\leq 4^{x-1}$ for all real $x\geq2$

How you prove this? I'm looking the Erdös proof from Bertrand Postulate and there are many things I don't get. Please don't hints, I'm newbie in combinatorics techniques. In the book I don't get ...
1
vote
1answer
49 views

How many ways are there to do this so that no officer picks $3$ students from the same high school?

There are $18$ students, three (distinct) students each from $6$ different high schools. There are $6$ admissions officers, one from each of $6$ colleges. Each of the officers successively picks a ...
7
votes
0answers
72 views

number of factorizations of distinct factors

Let $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ an integer with $p_i$ prime and $e_i \in \mathbb N$. The prime factorization can assumed to be known, i.e. we already know $p_1,\ldots,p_k$ and $e_1 , ...
1
vote
3answers
71 views

Number of different colourings of nodes

Consider a tree where each node has 2 subnodes, with a total of 7 nodes. So the maximum level of the tree is 2. Each node can be coloured white or black. Two colourings are equivalent if the one is ...
6
votes
1answer
50 views

The number of series over $\{0,1,2\}$ without repeating numbers

What is the number of series over $\{0,1,2\}$ with length $n$ without repeating the same number one after the other ($22$ is not allowed but $101$ is), that does not begin and end with the number $2$. ...
2
votes
2answers
47 views

Pigeonhole Principle question - sum of natural numbers

Let $f:\{1,2,...,15\} \rightarrow \Bbb N$ be a function such that $\sum_{i=1}^{15} f(i) =100$. $f(15+1)$ is defined to be $f(1)$. I have shown that $14\leq f(i)+f(i+1)$ for some $1\leq i \leq15$ ...
1
vote
1answer
48 views

Creating the Cayley table for $\mathbb{Z}_2 \times S_3$

Create the Cayley table for $\mathbb{Z}_2 \times S_3$ I know that the $\mathbb{Z}_2$ is: \begin{array}{c|cc} + & 0 & 1 \\\hline 0 & 0 & 1 \\ 1 & 1 & 0 \\ ...
1
vote
1answer
37 views

Interpretation of summations in regards to combinatorics

I've been studying for a final in combinatorics and ran into 3 different summations that have me stumped. 1) interpret the equation in terms of counting words. (Hint: $e^a$$e^b$$e^c$) $$e^{3x} = ...
6
votes
2answers
62 views

Find the number of ordered pairs $(a,b)$ if $\text{lcm}(a,b)=2^3 \cdot 3^5 \cdot 11^7 $

How many ordered pairs $(a,b)$ are there such that $$\text{lcm}(a,b)=2^3 \cdot 3^5 \cdot 11^7 $$ I tried using a number theoretic approach, but couldn't solve it. Moreover, it was given in ...
0
votes
1answer
33 views

find the coefficient of $x$ , in $P_{20}(x)$

Let $P_0(x) = x^3 + 313x^2 - 77x - 8$ , For integers $n \ge 1$ , define $P_n(x) = P_{n - 1}(x - n)$ , How do I find the coefficient of $x$ , in $P_{20}(x)$ ?
0
votes
2answers
59 views

In how many ways can you split six persons in two groups?

In how many ways can you split six persons in two groups? I think that I should use the binomial coefficient to calculate this but I dont know how. If the two groups has to have equal size, then ...
1
vote
1answer
37 views

thought were the same combinatorial

I was under the impression that $${52\choose 5!5!5!5!5!} = {52\choose 5}{47\choose 5}{42\choose 5}{37\choose 5}{32\choose 5} $$ Reason i ask is because i was trying to solve a simple number of ways ...
3
votes
2answers
46 views

Best Position In Line For Marble Draw

In a game you have $N$ players where player $N_i$ will play on turn $i$. On each turn the current player draws without replacement from a bag of marbles and will either win or lose depending on if ...
1
vote
0answers
79 views

the number of $n\times n$ matrices of 0's and 1's such that every row and column has three 1's [duplicate]

In the Example 1.1.3 of Stanley's book Enumerative Combinatorics Vol 1 (2nd edition), an explicit formula for the number $f(n)$ of $n\times n$ matrices of $0$'s and $1$'s such that every row and ...
0
votes
1answer
97 views

Combinatorics - Harvard Math Tournament.

For positive integers $x$, let $g(x)$ be the number of blocks of consecutive $1$’s in the binary expansion of $x$. For example, $g(19) = 2$ because $19 = 10011_2$ has a block of one $1$ at the ...
0
votes
2answers
47 views

Combination and Permutations: How many ways can an award be given?

Have this Math question which I'm helping my cousin with but struggling to make sense of the answer. Three prizes, one for English, one for French and one for Spanish, are to be awarded in a class of ...
3
votes
1answer
47 views

Two chess players, A and B, are going to play 7 games. There are three possible outcomes for each game, A wins, A loses, or Tie

Two chess players, A and B, are going to play 7 games. There are three possible outcomes for each game, A wins, A loses, or Tie Addtionally, a win is worth 1 point, draw 0.5 points and loss 0 points. ...
3
votes
1answer
50 views

Inclusion-Exclusion: INTELLIGENT permutations

How many ways are there to arrange the letters in INTELLIGENT with at least two consecutive pairs of identical letters? I got an answer of ...
1
vote
1answer
946 views

Predicting the number of orders from future customers

Tamara is reviewing recent orders at her deli to determine which meats she should order. She found that of 1,000 orders, 450 customers ordered turkey, 375 customers ordered ham and 250 customers ...
-3
votes
1answer
33 views

Count of numbers with exactly one digit $6$

How many integers from 1 to 100000 contain the digit 6 exactly once? Something like $6 + 6*9 + 6*9*9 + 6*9*9*9 + ...$?
9
votes
0answers
103 views

Is this determinant identity known?

Let $A$ be an $n \times n$ matrix that is 'almost upper triangular' in the following sense: entries on and above the main diagonal can be whatever they want, entries on the diagonal just below the ...
1
vote
1answer
29 views

Permutation with repetition and restriction

There are 5 red flowers, 4 blue flowers and 4 green ones. I must plant them so that no 2 red flowers are planted near each other. So I took all the possibilities (13!) and subtracted the ones where ...
0
votes
1answer
56 views

Generating function for set of binary strings of equal block length

Where blocks would be consecutive 0's or consecutive 1's. So 0000 would be a block of length 4. I'm not even sure how such a set would look? Would the following elements at least be in the set (so I ...
1
vote
0answers
40 views

Permutation and Combination Problem-word arrangement

There are three pieces of paper.In the three papers ,a string (non-empty) has to be written such that none of the string on any paper is prefix of some other string.Also alphabet size of characters ...
3
votes
0answers
44 views

NP-complete impossible to solve in $O(n)$

NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small ...
1
vote
1answer
35 views

Total no of closed loop paths in 3-by-3 grid

Rules for making a closed loop path: The path must pass through all points. The path have to pass each point only once. The path is formed by joining only consecutive points (defined below). The ...
0
votes
2answers
141 views

Bridge hand Combination/Permutation

A Bridge hand consists of 13 cards from a deck of 52 cards. In how many ways can a (bridge) hand consisting of 5 spades(♠), 4 hearts(♥), 4 diamonds(♦) and 0 clubs(♣) be selected?
1
vote
2answers
53 views

Counting problem for the integers

How many numbers $n < 100$ are not divisible by a square of any integer greater than $1$? Working through the above counting problem. I got $48$ using the Inclusion-Exclusion Principle, do ...
2
votes
4answers
36 views

Show that $\sum_{k = 0}^{4} (1+x)^k = \sum_{k=1}^5 \binom{5}{k}x^{k-1}$

Question: Show that: $$\sum_{k = 0}^{4} (1+x)^k = \sum_{k=1}^5 \binom{5}{k}x^{k-1}$$ then go on to prove the general case that: $$\sum_{k = 0}^{n-1} (1+x)^k = \sum_{k=1}^n \binom{n}{k}x^{k-1}$$ ...