This tag is for basic 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
4answers
335 views

In how many ways can three numbers be selected from the numbers $1,2,\dots,300$ such that their sum is divisible by $3$?

Can someone check which logic is finally correct?: In how many ways can three numbers be selected from the numbers $1,2,\dots,300$ such that their sum is divisible by $3$? I found different answers ...
0
votes
2answers
490 views

Want to classify project euler problem 31

I was thinking about Project Euler #31 yesterday, quoted below: In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation: 1p, 2p, 5p, ...
1
vote
1answer
48 views

Arithmetic progressions with coprime differences

Suppose we have finite number $n \geqslant 2$ of arithmetic progressions $\{x \equiv r_1 \pmod {d_1}\}, \ldots ,\{ x \equiv r_n \pmod {d_n}\}$ such that $\gcd(d_1, \ldots, d_n) = 1.$ Is true that ...
1
vote
1answer
33 views

hom many terms will consist only one $x$ and others $y$'s?

suppose I expand the product $(x_1+y_1)\dots(x_{20}+y_{20})$, I just want to know hommany terms will consist only one $x$ and others $y$'s?
11
votes
1answer
426 views

Circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them

I have a serious problem with this problem: Is it possible to Draw circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them !? Any help ...
3
votes
2answers
98 views

How many hexagons can be constructed by joining the vertices of a 15 sided polygon if none of the sides of the hexagon is also the side of the 15-gon.

How many hexagons can be constructed by joining the vertices of a 15 sided polygon if none of the sides of the hexagon is also the side of the 15-gon. My attempt First calculate in how many ways we ...
2
votes
3answers
36 views

Calculable labels/addresses for combinations?

Given a set of $n$ items (i.e., $\{X_1, X_2, X_3 ... X_n\}$), for all $\binom{n}{2}$ combinations, is there a function I can use to calculate unique labels in the range of $[1, \frac{n (n-1)}{2}]$, ...
1
vote
0answers
33 views

Functions of coefficients of univalent funtions

Suppose we have a univalent function on a disk $f(z):=\rho(a_1z+a_2z^2+\cdots)$ ($\rho>0$). Let $n\geq 1$. Let $I=(i_1, i_2, \ldots i_n)$ be a sequence of non-negative integers such that ...
2
votes
1answer
97 views

Show the following matrix recursion is symmetric

I need to show the following matrix equation is symmetric and I'm not sure where to start: $A_i=\sum_{j_1=1}^{i-2}2(i-j_1-1){i-2 \choose j_1-1}A_{j_1}\Big(\sum_{j_2=1}^{i-j_1-1}{i-j_1-2 \choose ...
0
votes
1answer
86 views

A problem regarding the proof of ${p^nk\choose p^n}\equiv k\mod p$, where $p\nmid k$.

In this proof, there is a statement where: $$(a+b)^{p^nk}\equiv (a^{p^n}+b^{p^n})^k\mod p$$ I understand this part. But then it expands both sides binomially, and compares coefficients of ...
0
votes
1answer
82 views

Variation on Birthday Problem - Probability that 47 of 191 students have birthdays on two conditions.

It's my birthday, and I figured I will create a problem based on birthdays that I myself am unable to solve! Assuming time is denoted by HH:MM:SS, MM/DD/YYYY, what is the probability that in a class ...
2
votes
1answer
111 views

pigeonhole principle - 100 points in $13\times18$ rectangle

Prove that you can't arrange 100 points inside a $13\times18$ rectangle so that the distance between any two points is at least 2. I tried many ways to divide the rectangle, but I can't get the parts ...
1
vote
0answers
100 views

A problem in the domino shuffling algorithm

The domino shuffling algorithm first appeared in the following paper by Propp and Kuperberg: Alternating-sign matrices and domino tilings They used this algorithm to give a fourth proof that the ...
0
votes
1answer
38 views

Number of (equivalence) relations fulfilling some additional conditions

let say I have $A=\{1,\dots,8\}$ I want to know the following things: what the number of relations on $A$? what the number of reflexivity relations on $A$? what the number of equivalence relations ...
1
vote
2answers
144 views

Combinatorical proof regarding multinomial coefficients

Okay, so combinatorics isn't exactly my strong suit, so bear with me. I'm asked to prove the following combinatorically: If n is a nonnegative integer and k is an integer, then $$\sum_j {n \choose ...
1
vote
2answers
77 views

Finding the number of solutions

I am trying to compare my answer with a friend's and we are both confident in our answers. But the problem is, they are different. So the problem goes: Suppose I have the equation $$x+y+z+w = 14$$ ...
3
votes
2answers
310 views

Algebraic proof of combinatorial identity

I would like to obtain the algebraic proof for the following identity. I already know the combinatorial proof but the algebraic proof is evading me. ...
4
votes
2answers
185 views

Filling a bag with fruits of four types, with constraints

Here's a diabolical math problem that I found. In how many ways can we fill a bag with n fruits subject to the following constraints? • The number of apples must be even. • The number of bananas ...
0
votes
2answers
60 views

Which is the best way to generate all $x_i$ where $\sum\limits_{i=1}^7 x_i = 1.0$?

I was wandering which is the best way to generate various combinations of $x_i$ such that $$\sum\limits_{i=1}^7 x_i = 1.0$$ where $ x_i \in \{0.0, 0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0\}$ I can ...
6
votes
0answers
93 views

Sum-Product Generating Functions

Let $A_n$ be a family of sequences $\{a_i\}_{i=1}^n$ of length $n$. I'll refer to sequence elements of $A_n$ as $a$. Then define $$G(z):=\sum_{a\in A_n}\prod_{i=1}^n(z+a_i).$$ Here's one possible ...
1
vote
2answers
171 views

A counting donuts problem involving combinatorics

A store carries three types of donuts: Strawberry, Chocolate and Glazed Suppose you bought $4$ of each kind and in addition, you have the option to apply sprinkles on your donuts. How many ways are ...
4
votes
3answers
133 views

How many members were there in the club?

The members of a chess club took part in a round robin competition in which each plays every one else once. All members scored the same number of points, except four juniors whose total scored ...
3
votes
0answers
163 views

Squaring rectangles

it is a nice high-school exercise to prove that a square can be tiled with n squares if and only if n=1, 4 or is any integer greater or equal to 6. A direct consequence is that any rectangle that can ...
3
votes
0answers
68 views

Finding the Average Difference in Ability Between Two Teams

Suppose you have $N$ football players, where $N$ is even, ranked in order of ability by the integers $\{1, \dots, N\}$ (where 1 is the best, N the worst) and they are randomly split into into two ...
0
votes
1answer
55 views

Balance it out (double factorial problem)

Amit was given a balance and n weights (where n is a positive integer) of weight 2^0, 2^1, 2^2,.... 2^(n-1). He is now assigned a task to place the weight that has not been placed on the balance, ...
0
votes
1answer
21 views

What's the maximum number of sums of $ak_1,..,ak_m, b\ell_1,…,b\ell_m$ needed to solve for $a$ or $b$?

Given a set of integer multiples of $a$ and $b$, $ak_1,..,ak_m, b\ell_1,...,b\ell_m$, what is the maximum number of finite sums of the multiples you can create such that no sum of all multiples of $a$ ...
2
votes
1answer
119 views

How many ways we can split $7$ green balls , $9$ red balls, and $10$ yellow balls to $2$ equal groups

I want to calculate how many ways we can split $7$ green balls , $9$ red balls, and $10$ yellow balls to $2$ equal groups. I want to check 2 options: The order is importent The order is not ...
0
votes
0answers
73 views

How many different 4-player UNO starting games are possible?

I know that for poker, there are $54!$ ways to arrange the cards in a poker deck which only contains unique cards. An UNO deck on the other hand has 108 cards. bit contains duplicates. It contains 25 ...
0
votes
2answers
71 views

No. of ways to choose n things from n alike “a” things n alike “b” things and n different things.

No. of ways to choose n things from n alike "a" things n alike "b" things and n different things. Answer is (n+2)2^n-1. But how to prove it..?
25
votes
5answers
612 views

Is it possible to put $+$ or $-$ signs in such a way that $\pm 1 \pm 2 \pm \cdots \pm 100 = 101$?

I'm reading a book about combinatorics. Even though the book is about combinatorics there is a problem in the book that I can think of no solutions to it except by using number theory. Problem: Is it ...
0
votes
1answer
58 views

How can I prove that the complement of the set of linear combinations of numbers with gcd 1 is finite?

Let $g_1,\ldots,g_n$ be natural numbers with gcd 1. Define $Q=\{a_1g_1+\cdots+a_ng_n| a_i\in\mathbb{N}\}$, what is the simplest way to prove that $\mathbb{N}\backslash Q$ is finite?
0
votes
1answer
75 views

How many ways to do n chose k such that the picks are non-decreasing?

Given n that represents the maximum value of all the numbers we can pick from such that 1 <= pick <= n Given k that represents how many numbers we must ...
1
vote
0answers
53 views

Smallest $r$ such that $\sum_{k=0,\,\, i+kr = qm}^{\lfloor (n-i)/r \rfloor} \binom{n}{i + kr} = 0 \pmod n$

I want to find the smallest positive integer $r$ such that $$\sum_{k=0,\,\, i+kr = qm}^{\lfloor (n-i)/r \rfloor} \binom{n}{i + kr} = 0 \pmod n$$ where $n=pq$, and every $i+kr = qm$ for some $m$ is ...
1
vote
1answer
372 views

What algorithm is a good to search a lotto design?

I'm interested what kind of algorithm would be suitable to find a lotto design? I saw that is has been proven that $L(39,7,4,7)=329$. This notation is explained in ...
1
vote
1answer
97 views

Cumulative abs sums

Let $s$ be an $n$-tuple of reals numbers satisfying $\sum_{k=1}^n s_k$. Denote by $\{c_i\}_{i=1}^n$ the permutations of this tuple $s$. Consider the tuple $$a_{i,j} = \left\{ ...
1
vote
4answers
5k views

How many 4 digit numbers are there which contains not more than 2 different digits? [duplicate]

How many 4 digit numbers are there which contains not more than 2 different digits? My attempt total no. of digits - the digits which have all different digits. i.e (9.10.10.10)-(9.9.8.7)=4464 ...
0
votes
1answer
139 views

Find the number of distinct arrangements.

There are 5white,4 yellow,3green,2blue & 1red ball.The balls are all identical except for colour. These are arranged in a line in 5 places.Find the number of distinct arrangements.! My attempt ...
2
votes
1answer
232 views

Find the number of sets $B$ such that $B \subset A$ , $|B|=m$, and the sum of the elements in $B$ is divisible by $p$.

Let $A=\{1,2,\ldots ,p\}$ where $p$ is a prime number. Find the number of sets $B$ such that $B \subset A$ , $|B|=m$, and the sum of the elements in $B$ is divisible by $p$.
3
votes
1answer
207 views

Ramsey Type problem (variant of people at a party)

There is $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\lfloor n/2\rfloor-1$ of them, each of whom either knows both or else ...
0
votes
1answer
40 views

A property of linear (error correcting) codes

Can someone prove the following problem? Let $C \subseteq \mathbb{F}_2^n$ be a linear code and let $$C^{\bot} = \{y \in \mathbb{F}_2^n \mid \langle x,y \rangle \mbox{ for all} \; x \in C\},$$ be the ...
1
vote
1answer
56 views

Need help with proving the recursion

Let $p_{k}(n)$ indicate the number of partitions of n into k parts. Prove: $$p_{k}(n) = p_{k-1}(n-1) + p_{k}(n-k)$$ Example: There are two partitions of $5$ into three parts. $5 = 3+1+1$ $5 = ...
4
votes
1answer
136 views

Counting bit flips

For $n, m \geq 1$, let $\Lambda^{n,m}$ be the set of all $(n+m)$-bit strings with exactly $n$ zeros and $m$ ones. For instance, $\Lambda^{2,3} = \{00111, 11100, 10011, 11001, 01110, 01011, 01101, ...
1
vote
1answer
90 views

Number of non-isomorphic connected graphs with m edges.

This might be an easy one, but I cant figure it out. Given $m$ edges how many connected (non-isomorphic) graphs can be drawn. Ofcourse there are no loops, multiple edges etc. I tried the recurrence ...
1
vote
1answer
143 views

$n$ balls into $k$ baskets, $n \geq k$, no empty baskets

I have $n$ balls and throw them into $k$ baskets. None of $k$ baskets should be empty. Which means each basket has at least one ball. Balls and baskets are not distinguishable. What is the number ...
0
votes
1answer
121 views

Have you seen this formula for factorial?

Let $p$ always be a prime. $n! = \prod_{p\leq n}p^{\lfloor \frac{n}{p}\rfloor}$. Then $\binom{n}{r} = \prod_{p\leq r}p^{\lfloor n/p \rfloor -\lfloor (n-r)/p \rfloor - \lfloor r/p \rfloor} \times ...
0
votes
0answers
56 views

What math do I need to find the lowest upper bound for this?

Let $n = pq$ for primes $p,q$. I want to find a lowest upper bound for the positive integer $r$ such that $$\displaystyle\sum_{i=0}^{\lfloor(n-m)/r\rfloor}\binom{n}{q(ri+m)} = 0 $$ modulo $n$. Where ...
1
vote
3answers
123 views

Logic behind “OR”? $P(\bar{A}\cap B) + P(\bar{B}\cap A)$ Vs $P(A \cup B)$

In a deck of $52$ cards , find the probability of drawing a king or a black card . Let probability of drawing a black card be P(A) Let probability of drawing a king be P(B) As drawing king , drawing ...
3
votes
3answers
898 views

Counting Question

Been wrestling with the following counting question for about an hour. I will explain my reasoning for counting in the question and I request any BETTER WAY to make this calculation or corrections if ...
2
votes
1answer
513 views

Natural deduction proof

So i been learning about Natural deduction and i got an exam coming up on it but i just want to understand a bit more about it. So far we have learnt 4 rules and thats all we need to know. We got : ...
0
votes
0answers
53 views

Condition for the number of distinct solutions over GF($q$)

Assume that we have $p$ sets $\left\{ {{m_i}} \right\}_{i = 1}^p$ with given cardinalities $\left\{ {{K_i}} \right\}_{i = 1}^p$, $1 \le {K_i} \le q$, where $q$ is a power of $2$. What I'm trying to do ...